package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC243 {

    static class Solution {
        /**
         * @param k: An integer
         * @return: all amicable pairs
         *          we will sort your return value in output
         */
        public List<List<Integer>> amicablePair(int k) {
            //关键点在于如何找到因子的和 , 判断条件是 i*i < number
            //能减少大量的无用循环计算

            List<List<Integer>> ans = new ArrayList<>();
            for (int i = 1; i <=k ; i++) {
                int cursum = f(i);
                if(cursum<=i || cursum >k) continue;

                if(i == f(cursum)){
                    ans.add(new ArrayList<>(Arrays.asList(i,cursum)));
                }
            }
            return ans;
        }

        public int f(int x){
            int ans =1;
            for (int i = 2; i*i <=x ; i++) {
                if(x%i ==0){
                    ans+=i+x/i;
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.amicablePair(300));
    }


}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有191条未读消息，请及时查看
243 · 相亲数
算法
简单
通过率
27%

题目
题解8
笔记
讨论41
排名
记录
描述
一对相亲数是指两个整数各自的所有有效因子（除了自己以外的因子）之和等于另外一个数。比如 (220, 284) 就是一对相亲数。因为：

220的所有因子：1+2+4+5+10+11+20+22+44+55+110 = 284
284的所有因子：1+2+4+71+142 = 220
给出整数 k，求 1~k 之间的所有相亲数对。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


对于返回的每对相亲数，要求数对中第一个数小于第二个。

样例
样例 1：

输入：300
输出：[[220,284]]
样例 2：

输入：220
输出：[]
标签
相关题目

147
水仙花数
简单

235
分解质因数
简单
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
15 分 00 秒
12345678910

控制台
        历史提交

 */